#include <vector>

using namespace std;

void SelectSort(vector<int> &array)
{
    int begin = 0, end = array.size() - 1;
    while (begin != end)
    {
        int mini = begin, maxi = end;
        for (int i = begin; i <= end; i++)
        {
            if (array[i] < array[mini])
                mini = i;
            if (array[i] > array[maxi])
                maxi = i;
        }
        swap(array[begin], array[mini]);
        if (begin == maxi)
                maxi = mini;
        swap(array[end], array[maxi]);
        begin++, end--;
    }
}